#pragma once

#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;

/*HJJ QQ479287006
 *给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？
 * 返回满足题意的二叉搜索树的种数。
输入：n = 3
输出：5
示例 2：

输入：n = 1
输出：1
 * */

//todo 这个东西本质是一个dp 但是这个是卡特兰数 可以利用组合数公式递归求一些试试

//C(n,k) = C(n - 1,k) + C(n - 1, k - 1);
// c(2 * n, n) / (n + 1).
int comm(int n, int k) {
    if (k > n)
        return 0;
    else if (n == k || k == 0)
        return 1;
    else
        return comm(n - 1, k) + comm(n - 1, k - 1);
}

int comm1(int n, int k) {
    int dp[100][100];
    dp[1][1] = 1;
    for (int i = 1; i < 100; i++) {
        dp[i][0] = 1;
    }
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= i; j++)
            dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
    }

    return dp[n][k];

}

//int numTrees(int n) {
//    return numTrees_d(2*n,n)/(n+1);
//}